package com.yoshino.leetcode.interview150.doublePoint;

import java.util.*;

class Solution {
    public boolean isPalindrome(String s) {
        int head = 0, tail = s.length() - 1;
        while (head < tail) {
            while (head < tail && !Character.isLetterOrDigit(s.charAt(head))) {
                head++;
            }
            while (head < tail && !Character.isLetterOrDigit(s.charAt(tail))) {
                tail--;
            }
            if (head < tail) {
                if (Character.toLowerCase(s.charAt(head)) != Character.toLowerCase(s.charAt(tail))) {
                    return false;
                }
                head++;
                tail--;
            }
        }
        return true;
    }

    public boolean isSubsequence(String s, String t) {
        if (s.length() > t.length()) {
            return false;
        }
        int sin = 0, tin = 0;
        while (sin < s.length() && tin < t.length()) {
            if (s.charAt(sin) == t.charAt(tin)) {
                sin++;
            }
            tin++;
        }
        return sin == s.length();
    }

    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{};
    }

    public int maxArea(int[] height) {
        int n = height.length;
        if (n == 2) {
            return Math.min(height[0], height[1]);
        }
        int left = 0, right = n - 1, res = 0;
        while (left < right) {
            int minH = Math.min(height[left], height[right]);
            res = Math.max(res, minH * (right - left));
            // 优化
            while (height[left] <= minH && left < right) {
                left++;
            }
            while (height[right] <= minH && left < right){
                right--;
            }
        } return res;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        // 两数之和 为 -第三数
        // -4 -1 -1 0 1 2
        Arrays.sort(nums);
        Set<List<Integer>> temp = new HashSet<>();
        for (int i = 0; i < nums.length - 2; ) {
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] == 0) {
                    temp.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    left++;
                    right--;
                    continue;
                }
                while (left < right && nums[left] + nums[right] + nums[i] < 0) {
                    left++;
                }
                while (left < right && nums[left] + nums[right] + nums[i] > 0) {
                    right--;
                }
            }
            i++;
            while (i < nums.length && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return new ArrayList<>(temp);
    }
}